#include <cstdlib>
#include "Sort.h"
#include "stack.h"
//直接插入排序
void InsertSort(int *a,int n){
    for (int i = 0; i <n-1 ; ++i) {
        //    假设[0,end]有序，end+1的位置插入进去，使[0,end+1]有序
        int end=i;
//    要插入的值
        int tmp=a[end+1];
        while (end>=0){
            if (a[end]>tmp){
                a[end+1]=a[end];
                end--;
            }else{
                break;
            }
        }
//        无论是找到了还是没有找到end在头的位置都插入
        a[end+1]= tmp;
    }
}
//打印数组
void PrintArray(int *a,int n){
    for (int i = 0; i < n; ++i) {
        printf("%d ",a[i]);
    }
    printf("\n");
}
//直接插入排序的优化
//先进行预排序，让数据接近有序
//希尔排序
void ShellSort(int *a,int n){
    int gap=n;
    while(gap>1){
        gap=gap/3+1;
        for (int i = 0; i <n-gap ; ++i) {
            int end=i;
            int tmp=a[end+gap];
            while (end>=0){
                if (a[end]>tmp){
                    a[end+gap]=a[end];
                    end-=gap;
                }else{
                    break;
                }
            }
            a[end+gap]=tmp;
        }
    }
}
//向下调整算法。前提是子树是小堆，通过循环建堆
void AdjustDown(int*a,int n,int root ){
    int parent=root;
    int child=parent*2+1;//默认是左孩子
    while(child<n){
//    选出左右孩子大的那个
        if (child+1<n&&a[child+1]<a[child]){
            ++child;//变成右孩子，使child指向小的那个
        }
        if (a[child]<a[parent]){
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }else{
//            小的比父节点都大
            break;
        }
    }
}
void AdjustUp(int*a,int n,int root ){
    int parent=root;
    int child=parent*2+1;//默认是左孩子
    while(child<n){
//    选出左右孩子大的那个
        if (child+1<n&&a[child+1]>a[child]){
            ++child;//变成右孩子，使child指向小的那个
        }
        if (a[child]>a[parent]){
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }else{
//            小的比父节点都大
            break;
        }
    }

}
void Swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
//堆排序
void HeapSort(int *a,int n){
//    把数组建成堆——————建堆，利用向下调整算法
//从最后一个树节点往上建堆，利用end求父节点
    for (int i =(n-1-1)/2; i >=0; --i) {
//        AdjustDown(a,n,i);
        AdjustUp(a,n,i);
    }
//    升排序，建大堆
    int end=n-1;
    while (end>0){
        //将第0个位置的值交换到尾部
        Swap(&a[0],&a[end]);
//        向下调整算法，选出次大的，每次调堆就可以了，不需要重新建堆
        AdjustUp(a,end,0);
//        尾部的位置已经排好，尾减一，不参与排序
        end--;
    }
}
//直接选择排序
void SelectSort(int*a,int n){
    int begin=0,end=n-1;
    while (begin<end){
        int mini=begin,maxi=end;
        for (int i = begin; i <=end ; ++i) {
            if (a[i]<a[mini]){
                mini=i;
            }
            if (a[i]>a[maxi]){
                maxi=i;
            }
        }
        Swap(&a[begin],&a[mini]);
        if (begin==maxi){
            maxi=end;
        }
        Swap(&a[maxi],&a[end]);
        ++begin,--end;
    }
}
void BubbleSort(int*a,int n){
    for (int j = 0; j <n ; ++j) {
        for (int i = 1; i < n-j; ++i) {
            if (a[i-1]>a[i]){
                Swap(&a[i-1],&a[i]);
            }

        }
    }
}
//快速排序，挖坑法
void QuickSort(int*a,int left,int right){
    if (left>=right){
        return;
    }
    int keyIndex= PartSort3(a,left,right);
//    三数取中
    //[left,right]
    //[left,pivot-1] pivot [pivot+1,right]
    //    左子区间和右子区间有序，我们就有序，分治递归
//    小区间优化
    if (keyIndex-1-left>10){
        QuickSort(a,left,keyIndex-1);
    }else{//右减左，再加一
        InsertSort(a+left,keyIndex-1-left+1);
    }
//    右区间
    if (right-(keyIndex+1)>10){
        QuickSort(a,keyIndex+1,right);
    }else{
        InsertSort(a+keyIndex+1,right-(keyIndex +1)+1);
    }
}
//三数取中
int GetMid(int *a,int left,int right){
    int mid=(left+right)>>1;
    if(a[left]<a[mid]){
        if (a[mid]<a[right]){//mid中间
            return mid;
        }else if (a[left]<a[right]){//mid最大，剩下的大的是中间值
            return right;
        }else{
            return left;//
        }
    }else{//a[left]>a[mid]
        if (a[mid]<a[right]){//mid最小
            return right;
        }else if (a[left]<a[right]){//mid最小，比较剩下的大小，小的是中间值
            return left;
        }else{
            return mid;
        }
    }
}
//单趟排序,挖坑法
int PartSort1(int *a,int left,int right){
    int index= GetMid(a,left,right);
    Swap(&a[index],&a[left]);
    int begin=left,end=right;
    int pivot=begin;
    int key=a[begin];
    while (begin<end){
        while (a[end]>=key&&begin<end){
            --end;
        }
//        小的放到左边的坑里
        a[pivot]=a[end];
        pivot=end;
//        左边找大，放到右边坑位，自己形成新的坑
        while (a[begin]<=key&&begin<end){
            ++begin;
        }
        a[pivot]=a[begin];
        pivot=begin;
    }
    pivot=begin;
    a[pivot]=key;
    return pivot;
}
//指针法
int PartSort2(int *a,int left,int right){
    int index= GetMid(a,left,right);
    Swap(&a[index],&a[left]);
    int begin=left,end=right;
    int keyi=begin;
    while (begin<end){
//        找小
        while(begin<end&&a[end]>=a[keyi]){
            --end;
        }
//        找大
        while(begin<end&&a[begin]<=a[keyi]){
            ++begin;
        }
        Swap(&a[end],&a[begin]);
    }
    Swap(&a[keyi],&a[begin]);
    return begin;//返回相遇的位置
}
//前后指针法
int PartSort3(int *a,int left,int right){
    int index= GetMid(a,left,right);
    Swap(&a[index],&a[left]);

    int keyi=left;
    int prev=left,cur=left+1;
    while (cur<=right){
        if (a[cur]<a[keyi]){
            ++prev;
            Swap(&a[prev],&a[cur]);
        }
        ++cur;
    }
    Swap(&a[keyi],&a[prev]);
    return prev;
}
//归并排序
void _MergeSort(int *a,int left,int right,int* tmp){
    if (left>=right){
        return;
    }
    int mid=(left+right)>>1;
    //假设[left,mid] [mid+1,right]有序，我们就可以归并
    _MergeSort(a,left,mid,tmp);
    _MergeSort(a,mid+1,right,tmp);
//    归并
//两段区间的开始和结束
    int begin1=left,end1=mid;
    int begin2=mid+1,end2=right;
    int index=left;
//    比较两个数组的大小，把小的拷贝到tmp中；
    while (begin1<=end1&&begin2<=end2){
        if (a[begin1]<a[begin2]){
            tmp[index++]=a[begin1++];
        }else{
            tmp[index++]=a[begin2++];
        }

    }
//    如果有剩余的元素，就直接把剩下的元素拷贝到tmp中
    while (begin1<=end1){
        tmp[index++]=a[begin1++];
    }
    while (begin2<=end2){
        tmp[index++]=a[begin2++];
    }
    //拷贝回去
    for (int i = left; i <=right ; ++i) {
        a[i]=tmp[i];
    }
}
void MergeSort(int *a,int n){
    int* tmp=(int*)malloc(sizeof (int)*n);
    _MergeSort(a,0,n-1,tmp);
}
//快拍排序，非递归，因为递归会导致栈溢出
void QuickSortNoR(int*a,int n){
    ST st;
    STInit(&st);
    StackPush(&st,n-1);
    StackPush(&st,0);
    while(!StackEmpty(&st)){
        int left= StackTop(&st);
        StackPop(&st);

        int right= StackTop(&st);
        StackPop(&st);

        int keyIndex=PartSort1(a,left,right);
        //[left,keyIndex-1]keyIndex[keyIndex+1,right]
        if (keyIndex+1<right){
            StackPush(&st,right);
            StackPush(&st,keyIndex+1);

        }

        if (left<keyIndex-1){
            StackPush(&st,left);
            StackPush(&st,keyIndex-1);
        }
    }
    Destory(&st);
}
//归并排序非递归
void MergeSortNoR(int *a, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n); // 临时数组
    int gap = 1; // 初始分组大小

    while (gap < n) { // 外层循环控制 gap 的增长
        for (int i = 0; i < n; i += gap * 2) { // 内层循环处理每个分组
            // [i, i+gap-1], [i+gap, i+2*gap-1]
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            // 检查边界，防止越界
            if (end1 >= n) end1 = n - 1; // 第一组超出范围
            if (begin2 >= n) { // 第二组完全超出范围
                begin2 = n;
                end2 = n - 1;
            }
            if (end2 >= n) end2 = n - 1; // 第二组部分超出范围

            int index = begin1; // 临时数组的起始位置

            // 归并两个有序区间
            while (begin1 <= end1 && begin2 <= end2) {
                if (a[begin1] < a[begin2]) {
                    tmp[index++] = a[begin1++];
                } else {
                    tmp[index++] = a[begin2++];
                }
            }

            // 拷贝剩余元素
            while (begin1 <= end1) {
                tmp[index++] = a[begin1++];
            }
            while (begin2 <= end2) {
                tmp[index++] = a[begin2++];
            }
        }

        // 将临时数组的结果拷贝回原数组
        for (int j = 0; j < n; j++) {
            a[j] = tmp[j];
        }

        gap *= 2; // 更新分组大小
    }

    free(tmp); // 释放临时数组
}
